﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Algoritmia.DataStructures.Lists;
using Algoritmia.DataStructures.Queues;
using Algoritmia.Problems.Geometry;
using Algoritmia.Problems.Geometry.ConvexHull;

namespace Demos.Problems
{
    public class ComparaPuntos : IComparer<Tuple<double, double>>
    {
        private Tuple<double, double> p;

        public ComparaPuntos(Tuple<double, double> p)
        {
            this.p = p;
        }

        public int Compare(Tuple<double, double> q1, Tuple<double, double> q2)
        {
            var tan1 = Math.Atan2(p.Item2 - q1.Item2, p.Item1 - q1.Item1);
            var x1 = q1.Item1;
            var t1 = new Tuple<double, double>(tan1, x1);

            var tan2 = Math.Atan2(p.Item2 - q2.Item2, p.Item1 - q2.Item1);
            var x2 = q2.Item1;
            var t2 = new Tuple<double, double>(tan2, x2);

            return Comparer<Tuple<double, double>>.Default.Compare(t1, t2);
        }
    }

    public class ObservableGrahamConvexHullFinder
    {
        public event ObservableQuickhull.Linea NuevaLinea;

        public Algoritmia.DataStructures.Lists.IList<int> find(Algoritmia.DataStructures.Lists.IList<Tuple<double, double>> S)
        {
            var S1 = S.Select(pt => new Point2D(pt)).ToList();
            var min_y = S[0].Item2;
            foreach (var pt in S.Where(pt => pt.Item2 < min_y))
            {
                min_y = pt.Item2;
            }
            var pts = S.Where(pt => pt.Item2 == min_y).ToList();
            var p = pts[0];
            foreach (var pt in pts.Where(pt => pt.Item1 > p.Item1))
            {
                p = pt;
            }
            var qS = S.Where(q => q != p).ToList();
            var comparador = new ComparaPuntos(p);
            qS.Sort(comparador);
            S = new ArrayList<Tuple<double, double>>(new List<Tuple<double, double>>() { p }.Concat(qS));
            var Q = new Lifo<int>();
            Q.Push(0);
            Q.Push(1);
            Q.Push(2);
            for (int pi = 3; pi < S.Count; pi++)
            {
                var pj = Q.ElementAt(Q.Count-1);
                var pk = Q.ElementAt(Q.Count - 2);
                while (!Utils.Left(new Point2D(S[pk]), new Point2D(S[pj]), new Point2D(S[pi])))
                {
                    Q.Pop();
                    pj = Q.ElementAt(Q.Count - 1);
                    pk = Q.ElementAt(Q.Count - 2);
                }
                Q.Push(pi);
            }
            var listaRetorno = new ArrayList<int>();
            for (var i = 0; i < Q.Count; i++)
            {
                listaRetorno.Add(S1.IndexOf(new Point2D(S[Q.Pop()])));
            }
            return listaRetorno;
        }
    }

    
}
